package com.lw.leetcode.arr.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2448. 使数组相等的最小开销
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/24 13:16
 */
public class MinCost {

    public static void main(String[] args) {
        MinCost test = new MinCost();

        // 8
//        int[] nums = {1, 3, 5, 2};
//        int[] cost = {2, 3, 1, 14};

        // 0
//        int[] nums = {2, 2, 2, 2, 2};
//        int[] cost = {4, 2, 8, 1, 3};

        //
        int ls = 50000;
        int limt = 1000000;
        int[] nums = Utils.getArr(ls, 1, limt);
        int[] cost = Utils.getArr(ls, 1, limt);

        long l = test.minCost(nums, cost);
        System.out.println(l);
    }

    public long minCost(int[] nums, int[] cost) {
        int length = nums.length;
        long[] arr = new long[length];
        long sum = 0;
        for (int i = 0; i < length; i++) {
            sum += cost[i];
            arr[i] = ((long) nums[i] << 32) + cost[i];
        }
        Arrays.sort(arr);
        sum >>= 1;
        long s = 0;
        int t = 0;
        for (long l : arr) {
            int v = (int) l;
            s += v;
            if (s >= sum) {
                t = (int) (l >> 32);
                break;
            }
        }
        long min = 0;
        for (int i = 0; i < length; i++) {
            min += Math.abs(nums[i] - t) * (long) cost[i];
        }
        return min;
    }

}
